home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 October: Mac OS SDK / Dev.CD Oct 00 SDK1.toast / Development Kits / Mac OS / AIAT / Headers / Analysis / LetterTree.h < prev    next >
Encoding:
Text File  |  1998-04-16  |  3.6 KB  |  138 lines  |  [TEXT/CWIE]
  1.  
  2. //
  3. //    LetterTree.h
  4. //    Copyright © 1994 - 1998 Apple Computer, Inc.
  5.  
  6. //    DESCRIPTION:
  7.     
  8. //    This file implements the classes LetterTree and LetterNodeChain.
  9. //    LetterTree stores words and can perform lookups relatively quickly.
  10. //  It is relatively bulky and therefore probably not suitable for very large collections.
  11.     
  12.     
  13. //    IMPLEMENTATION:
  14.     
  15. //    LetterTree stores an array (a-z or A-Z) of initial letters.
  16. //    Each of those, when not NULL, is a pointer which points to an instance
  17. //    of LetterNodeChain.
  18.     
  19. //    LetterNodeChain encodes a single letter, a next node, and a child node.
  20. //    Instances in a chain (via next) are at the same level of the tree (letters at the same position
  21. //        in the word).
  22. //    Instances in a chain (via child) encode characters one level later in the word.
  23.     
  24. //    A sample tree encoding the words "about","around", "art", and "duh" would be:
  25. //    [TLNC == LetterNodeChain]
  26.     
  27. //    <LetterTree>
  28. //        [A] ->    <TLNC: 'B'>
  29. //                child->    <TLNC: 'O'>
  30. //                        child->    <TLNC: 'U'>
  31. //                                child->    <TLNC: 'T'>
  32. //                                        child-> <TLNC: '\0'> (path encoding "ABOUT")
  33. //                next->    <TLNC: 'R'>
  34. //                        child-> <TLNC: 'T'>
  35. //                                child-> <TLNC: '\0'> (path encoding "ART")
  36. //                                next->    <TLNC: 'O'>
  37. //                                        child->    <TLNC: 'U'>
  38. //                                                child->    <TLNC: 'N'>
  39. //                                                        child->    <TLNC: 'D'>
  40. //                                                                child-> <TLNC: '\0'>
  41. //                                                                    (path encoding "AROUND")
  42. //        [D] ->    <TLNC: 'U'>
  43. //                child->    <TLNC: 'H'>
  44. //                        child->    <TLNC: '\0'> (path encoding "DUH")
  45. //                        
  46. //    
  47. //    This class assumes words are canonized (upper/lower settable with a #define).
  48. //    
  49. //    currently uses an unsigned 8-bit char--not compatible with 16-bit characters.
  50.  
  51. #pragma once
  52.  
  53. #ifndef LETTERTREE_h
  54. #define LETTERTREE_h
  55.  
  56. #pragma import on
  57.  
  58. #if PRAGMA_STRUCT_ALIGN
  59.     #pragma options align=power
  60. #endif
  61.  
  62. #include "IAStorable.h"
  63.  
  64. class IACharStream;
  65. class StringTerm;
  66.  
  67. #pragma IA_BEGIN_EXPORTS
  68.  
  69. class LetterNodeChain {
  70.     public:
  71.     
  72.                 LetterNodeChain( byte letterParam );
  73.         void    DeleteChain();
  74.         
  75.         void    Add( byte *newWord, uint32 wordLen );
  76.         bool    Contains( byte *word );
  77.     
  78.         // returns the number of bytes in an objects serialization
  79.         uint32        StoreSize( uint32 currentWordSize );
  80.         // serializes the object to output, writing StoreSize() bytes to output
  81.         void        Store(IAOutputBlock* output, byte *currentWord, unsigned short position);
  82.  
  83.     private:
  84.         unsigned char letter;
  85.         LetterNodeChain *child;
  86.         LetterNodeChain    *next;
  87.     
  88.         LetterNodeChain *ProperNodeInChain( byte letterParam );
  89.         LetterNodeChain *ProperNodeInChainAddIfNone( byte letterParam );
  90.         void    AddChildren( byte *newWord, uint32 wordLen );
  91.         bool    ChildContains( byte *word );
  92.         
  93.         
  94. };
  95.  
  96. const unsigned short kHowManyLetters = ('z' - 'a' + 1);
  97.  
  98. class LetterTree : public IAStorable {
  99.     
  100.     public:
  101.     
  102.                         LetterTree();
  103.                         LetterTree( IAInputBlock *block );
  104.                         ~LetterTree() { EmptyTree(); };
  105.         void                EmptyTree();
  106.         
  107.         virtual IAStorable*    DeepCopy() const;
  108.  
  109.     // returns the number of bytes in an objects serialization
  110.         virtual uint32        StoreSize() const;
  111.     // serializes the object to output, writing StoreSize() bytes to output
  112.         virtual void        Store(IAOutputBlock* output) const;
  113.     // deserializes and returns a new object -- reading StoreSize() bytes from input
  114.         virtual IAStorable*    Restore(IAInputBlock* input) const;
  115.     
  116.         void                LoadFromFile( char *filePath );
  117.         void                LoadFromStream( IACharStream *stream );
  118.  
  119.         void                Add( StringTerm *newWord );
  120.         bool                Contains( byte *word );
  121.         bool                Contains( StringTerm *term );
  122.     
  123.         static const unsigned short kMaxCharsInWord;
  124.     
  125.     private:
  126.         LetterNodeChain *children[kHowManyLetters];
  127.  
  128. };
  129.  
  130. #pragma IA_END_EXPORTS
  131.  
  132. #if PRAGMA_STRUCT_ALIGN
  133.     #pragma options align=reset
  134. #endif
  135.  
  136. #pragma import reset
  137.  
  138. #endif